Homomorphic Hidings
m0t0k1ch1.icon < Zcash のブログ記事を読んで zk-SNARKs で用いられている技術について勉強していくシリーズ
---.icon
以下を満たすような$ E(x)が HH(Homomorphic Hidings)。
ほとんどの$ xについて、$ E(x)から$ xを見つけるのが困難
入力が異なれば出力も異なる:$ x \neq yであれば$ E(x) \neq E(y)
もし$ E(x)と$ E(y)を知っていたら、$ xと$ yの 演算 の HH が生成できる
例えば、$ E(x)と$ E(y)から$ E(x + y)が計算できるなど
普通の加算で上記の条件を満たすことはできないので、有限群 を考える必要がある。
$ nを整数とする。集合$ \{0, \ldots, n - 1\}について「加算の結果に$ \mod nを適用する」という演算を適用すると、演算の結果は$ \{0, \ldots, n - 1\}の中に収まる。例えば、$ 2 + 3 = 1 \mod 4となる。このような群$ \{0, \ldots, n - 1\}を$ Z_nとする。
例えば$ Z_7の場合、単位元は$ 0、$ 1の逆元は$ 6、$ 2の逆元は$ 5、などなど。
$ pを素数とする。集合$ \{1, \ldots, p - 1\}について「乗算の結果に$ \mod pを適用する」という演算を適用すると、演算の結果は$ \{1, \ldots, p - 1\}の中に収まる。例えば、$ 2 \cdot 4 = 1 \mod 7となる。このような群$ \{1, \ldots, p - 1\}を$ Z_p^*とする。
例えば$ Z_7^*の場合、単位元は$ 1、$ 2の逆元は$ 4、$ 3の逆元は$ 5、などなど。
m0t0k1ch1.icon < $ pが素数なのは、$ 0が出てこないようにするため
m0t0k1ch1.icon < 例えば$ p = 4とすると、$ 2 \cdot 2 = 0 \mod 4
$ Z_p^*は次のような性質を持つ。
1. 巡回群 である:$ Z_p^*の元の中に 生成元 と呼ばれる元$ gが存在し、$ Z_p^*の全ての元は$ g^a($ a \in Z_{p - 1})で表すことができる($ g^0 = 1)
2. $ Z_p^*の中では 離散対数問題が困難 である:$ pが十分に大きいとき、$ Z_p^*の元 $ hから$ g^a = h \mod pとなるような$ a($ a \in Z_{p - 1})を見つけるのが困難
3. $ g^a \cdot g^b = g^{a + b \mod p - 1}($ a, b \in Z_{p - 1})
すなわち、$ x \in Z_{p - 1}とすると、$ E(x) = g^xは $ Z_p^*においては HH となる。理由は以下。
HH の 1 つ目の条件:上記 2. によって満たされる
HH の 2 つ目の条件:上記 1. によって満たされる
HH の 3 つ目の条件:上記 3. より、$ E(x + y) = g^{x + y \mod p - 1} = g^x \cdot g^y = E(x) \cdot E(y)
m0t0k1ch1.icon < $ Z_p^*の話をしているが、$ x, y \in Z_{p - 1}だから、$ x + yは$ Z_{p - 1}の演算を適用しているという感じ?
m0t0k1ch1.icon < $ Z_p^*の性質 3. については、以下の具体例を参考に、$ gが巡回していることを意識するとイメージしやすい
例えば$ Z_7^* = \{1, 2, 3, 4, 5, 6\}の場合について考えてみる。Go で雑に以下のようなコードを書いてみた。
code:main.go
package main
import "fmt"
func main() {
z := []int{1, 2, 3, 4, 5, 6}
for _, e := range z {
result := make([]int, 6)
for i := 0; i <= 5; i++ {
if i == 0 { // e^0
} else {
resulti = mulmod7(resulti-1, e) }
}
fmt.Println(e, ":", result)
}
}
func mulmod7(a, b int) int {
return a * b % 7
}
実行結果は以下。
code:result.txt
$ 3と$ 5は生成元$ gであることが分かる。巡回している様子がわかりやすい。